import java.util.ArrayDeque;
import java.util.Deque;

public class Leetcode85 {
    public int maximalRectangle(char[][] matrix) {
        if(matrix.length==0){
            return 0;
        }
        int[] heights = new int[matrix[0].length];
        int res = 0;
        for(int i=0;i<matrix.length;i++){
            for(int j =0;j<matrix[0].length;j++){
                int cur = i;
                int height = 0;
                if(i==0){
                    heights[j] = matrix[i][j]=='1'?1:0;
                }else{
                    if(matrix[i][j]=='0'){
                        heights[j] = 0;
                    }else{
                        while(cur>=0){
                            if(matrix[cur][j]=='1'){
                                cur--;
                                height++;
                            }else {
                                break;
                            }
                        }
                        heights[j] = height;
                    }
                }
            }
            res = Math.max(res,getMaxSize(heights));
        }
        return res;

    }

    public int getMaxSize(int[] heights) {
        int len = heights.length;
        if(len==0){
            return 0;
        }
        if(len ==1){
            return heights[0];
        }
        int[] newHeight = new int[len+2];
        newHeight[0] = 0;
        newHeight[len+1] = 0;
        for(int i = 1;i<len+1;i++){
            newHeight[i] = heights[i-1];
        }
        int res = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        stack.addLast(0);

        for(int i =1;i<len+2;i++){
            while(newHeight[i]<newHeight[stack.peekLast()]){
                int curHeight = newHeight[stack.pollLast()];
                int width = i - stack.peekLast() -1;
                res = Math.max(res,curHeight*width);
            }
            stack.addLast(i);
        }

        return res;
    }

    public static void main(String[] args) {
// [["1","0","0","0","1"],["1","1","0","1","1"],["1","1","1","1","1"]]
        char[][] c = {{'1','0','0','0','1'},{'1','1','0','1','1'},{'1','1','1','1','1'}};
        Leetcode85 leetcode85 = new Leetcode85();
        leetcode85.maximalRectangle(c);
    }
}
